package part2;

import java.util.*;

/**
 * @Author: shaochong
 * @Date: 2021/8/13
 * @Description:
 */
public class Solution17 {
    public static List<String> letterCombinations(String digits) {
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        List<String> ansList = new ArrayList<>();
        int index = 0;
        List<Character> ans = new ArrayList<>();

        dfs(ansList, digits, map, index, ans);
        return ansList;
    }

    public static void dfs(List<String> ansList, String digits, Map<Character, String> map, int index, List<Character> ans) {
        if (index == digits.length() ) {
            StringBuilder sb = new StringBuilder();
            for (char c: ans) {
                sb.append(c);
            }
            ansList.add(sb.toString());
            return;
        }
        String s = map.get(digits.charAt(index));
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            ans.add(c);
            dfs(ansList, digits, map, index + 1, ans);
            ans.remove(ans.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));
    }
}
